Level 2: XIPHEREHPIX's Reckless Mistake (crypto)

In this level, we are given a C program that takes in a password and compares it against a SHA256 hash. If the password is correct, it is transformed into 16 byte AES key and used to decrypt some AES-GCM encrypted string.

The password must also be 40 characters long, which is impossible to bruteforce:

password_length = input_password(password);
if (password_length < 40) {
    printf("The password should be at least 40 characters as per PALINDROME's security policy.\n");
    exit(0);
}

Therefore, the most likely avenue of attack is the key derivation algorithm:

void accumulate_xor(uint256_t *result, uint256_t *arr_entry) {
    result->a0 ^= arr_entry->a0;
    result->a1 ^= arr_entry->a1;
    result->a2 ^= arr_entry->a2;
    result->a3 ^= arr_entry->a3;

}
void initialise_key(unsigned char *key, char *password, int password_length) {
    const char *seed = "PALINDROME IS THE BEST!";
    int i, j;
    int counter = 0;

    uint256_t *key256  = (uint256_t *)key;

    key256->a0 = 0;
    key256->a1 = 0;
    key256->a2 = 0;
    key256->a3 = 0;

    uint256_t arr[20] = { 0 };
    
    // Stage 1: Key material generation

    calculate_sha256((unsigned char *) arr, (unsigned char *) seed, strlen(seed));

    for (i = 1; i < 20; i++) {
        calculate_sha256((unsigned char *)(arr+i), (unsigned char *) (arr+i-1), 32);
    }
    
    // Stage 2: Key material selection
    
    for (i = 0; i < password_length; i++) {
        int ch = password[i];
        for (j = 0; j < 8; j++) {
            counter = counter % 20;

            if (ch & 0x1) {
                accumulate_xor(key256, arr+counter);
            }

            ch = ch >> 1;
            counter++;
        }
    }
}

The key derivation algorithm works in two stages:

1. Key material generation: 20 SHA256 hashes are derived from the original seed. Since the original seed is a constant string, this stage always produces the same result, independent of the input key.
2. Key material selection: The key is initialized to all 0s. Then, if the i-th bit of the password string is set, the key is XORed with the i%20th SHA256 hash generated in stage 1.

Since the input password is at least 40 bytes long, and the output AES key is only 16 bytes long, stage 2 must discard information in some way. The only question is how, and how much?

The answer lies in the XOR operation, which has the useful property that XORing something with itself results in 0.

Suppose I have an initial key state K, and the password string has bits 0 and 20 set. Since 0 % 20 = 20 % 20 = 0 , I would XOR K with the 0-th hash twice.

But since I'm XORing something with itself, this cancels out and the end result is still K.

Therefore, whether the n-th hash is included 0, 2, 4, or 6 times doesn't matter, the only thing that matters is if its included an even or odd number of times.

Thus, there are only 2^20 possible keys, far less than the 2^128 of a completely random AES key.

Since most of the decryption code is already included, I modified it slightly to bruteforce the key:

const char *seed = "PALINDROME IS THE BEST!";
int i, j;

uint256_t *key256 ;

uint256_t arr[20] = { 0 };

// Since the result is the same every time, we just need to run it once
void init(){
    calculate_sha256((unsigned char *) arr, (unsigned char *) seed, strlen(seed));

    for (i = 1; i < 20; i++) {
        calculate_sha256((unsigned char *)(arr+i), (unsigned char *) (arr+i-1), 32);
    }
}

void initialise_key(unsigned char *key, int n) {
    key256 = (uint256_t *)key;

    key256->a0 = 0;
    key256->a1 = 0;
    key256->a2 = 0;
    key256->a3 = 0;

    for (j = 0; j < 20; j++) {
        if(n & (1<<j)){
            accumulate_xor(key256, arr+j);
        }
    }
}

int main(int argc, char **argv)
{
    unsigned char key[32];
    init();
    
    for(int n = 0; n < 1048576; n++) {
        initialise_key(key, n);
        show_welcome_msg(key);
    }
}

➜ gcc solve.c -o solve -lcrypto
➜ ./solve | strings | grep TISC
TISC{K3ysP4ce_1s_t00_smol_d2g7d97agsd8yhr}